package offer

import (
	. "GoLeetcode/common"
	"fmt"
)

/*
时间复杂度：O()
空间复杂度：O()

*/
func lenLongestFibSubseq(arr []int) int {
	hash := make(map[int]int)
	ans := 0
	dp := make([]int, len(arr))
	dp[0] = 1
	hash[arr[0]] = 0
	for i := 1; i < len(arr); i++ {
		for j := i - 1; j >= 0; j-- {
			diff := arr[i] - arr[j]
			if pos, ok := hash[diff]; ok && pos < j {
				dp[i] = Max(dp[i], dp[pos]+2)
			}
		}
		ans = Max(ans, dp[i])
		hash[arr[i]] = i
	}
	fmt.Println(dp)
	return ans
}
